package com.hfb.mashibing.alip8.diamondsquarealgorithm.class06;


/**  题目：求x树的最小高度
 *
 * 5种情况：空树；没有子树；只有左/右子树；有俩子树
 *
 * 方法：①递归 ② Morris遍历
 *
 *
 */
public class test02_MinHeight {

    private static class Node {
        public int value;
        Node left;
        Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 求x树的最小高度
     * @param x
     * @return
     */
    public static int minHeight1(Node head) {
        if (head == null){
            return 0;
        }
        return p(head);
    }

    /**
     * 求x树的最小高度
     * @param x
     * @return
     */
    public static int p(Node x){
        if (x.left == null && x.right==null) {
            return 1;
        }
        int leftH = Integer.MAX_VALUE;
        if (x.left!=null){
            leftH = p(x.left);
        }
        int rightH = Integer.MAX_VALUE;
        if(x.right!=null){
            rightH = p(x.right);
        }
        return 1 + Math.min(leftH, rightH);
    }
    // 用Morris遍历改写
    public static int minHeight2(Node head){
        if (null == head){
            return 0;
        }
        Node cur = head;
        Node mostRight = null;
        int curLevel = 0;
        int minHeight = Integer.MAX_VALUE;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight!=null){
                int leftHeight = 1;
                while(mostRight.right!=null&&mostRight.right!=cur){
                    leftHeight++;
                    mostRight = mostRight.right;
                }
                if (mostRight.right ==null){ // 第一次到达
                    curLevel++;
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                 }else{ // 第二次到达
                    if (mostRight.left !=null){
                        minHeight = Math.min(minHeight, curLevel);
                    }
                    curLevel -= leftHeight;
                    mostRight.right = null;
                }
            }else{  // 只有一次到达
                curLevel ++;
            }
            cur = cur.right;
        }
        int finalRight = 1;
        cur = head;
        while (cur.right!=null){
            finalRight++;
            cur = cur.right;
        }
        if (cur.left==null && cur.right==null){
            minHeight = Math.min(minHeight,finalRight);
        }
        return minHeight;
    }



}
